package com.zet.algorithm;

/**
 * 冒泡排序
 *
 * 冒泡排序的时间复杂度是O(N2)：假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，
 * 需要遍历多少次呢？N-1次！因此，冒泡排序的时间复杂度O(N2)。

 冒泡排序是稳定的算法：它满足稳定算法的定义；所谓算法稳定性指的是对于一个数列中的两个相等的数a[i]=a[j]，
 在排序前,a[i]在a[j]前面，经过排序后a[i]仍然在a[j]前，那么这个排序算法是稳定的。
 * @Author: zet
 * @Date: 2018-03-24 10:54
 */
public class BubbleSort{

    /**
     * 方式1：排序
     * @param arr 待排序数组
     * @return 有序数组
     */
    public static int[] sort1(int[] arr) {
        int len = arr.length;
        for (int i = len -1 ; i > 0 ; i--) {
            for (int j = 0; j < i; j++) {
                 if (arr[j] > arr[j+1]) {
                     int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }


    /**
     * 方式1：排序（优化版）
     * @param arr 待排序数组
     * @return 有序数组
     */
    public static int[] sort2(int[] arr) {
        int len = arr.length;
        boolean isSort = true;
        for (int i = len -1 ; i > 0 ; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    isSort = false;
                }
            }
            if (isSort)
                break;
        }
        return arr;
    }

}
